package com.lfg.leetcode.leetcode200;

import java.util.*;

public class No207canFinish {

    public static void main(String[] args) {
        boolean ret = canFinish(3, new int[][]{new int[]{0, 2}, new int[]{2, 0}, new int[]{1, 2}});
        System.out.println(ret);
    }


    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses <= 1) {
            return true;
        }
        Queue<Integer> root = new LinkedList<>();
        Map<Integer, List<Integer>> nextMap = new HashMap<>();
        Map<Integer, Integer> cntMap = new HashMap<>();

        for (int[] data : prerequisites) {
            List<Integer> nextList = nextMap.get(data[1]);
            if (nextList == null) {
                nextList = new ArrayList<>(numCourses);
                nextMap.put(data[1], nextList);
            }
            nextList.add(data[0]);
            Integer cnt = cntMap.get(data[0]);
            if (cnt == null) {
                cntMap.put(data[0], 1);
            } else {
                cntMap.put(data[0], cnt + 1);
            }
        }
        for (int i = 0; i < numCourses; i++) {
            Integer cnt = cntMap.get(i);
            if (cnt == null || cnt == 0) {
                root.add(i);
            }
        }

        while (!root.isEmpty()) {
            Integer course = root.poll();
            List<Integer> nextList = nextMap.get(course);
            if (nextList == null || nextList.isEmpty()) {
                continue;
            }
            for (Integer next : nextList) {
                Integer value = cntMap.get(next);
                if (null == value) {
                    continue;
                }
                if (value == 1) {
                    cntMap.remove(next);
                    root.offer(next);
                } else {
                    cntMap.put(next, value - 1);
                }
            }
        }


        return cntMap.isEmpty();
    }

}
